The present invention generally relates to a technique for calculating a hash value and, more particularly, to a technique for calculating a hash value capable of generating one or more, in particular, a plurality of hash functions by changing a position for selecting a bit.
As a method of storing keys in a hash table with high space efficiency, there is known a method called multi-level hash table (MHT) that divides a hash table into multiple blocks by using different hash functions to improve the space efficiency (see Non Patent Literatures 1 and 2 described below).
Japanese Patent JP2004-229163A describes a fixed-length data retrieving device including: hash calculating means for calculating first and second hash values of input fixed-length data using two kinds of hash functions; a data table memory including N (N is an integer equal to or larger than 2) memory banks and storing a data table in which a large number of fixed-length data are retained; a pointer table memory storing a main memory pointer table in which memory addresses of storage destinations of the fixed-length data are retained using the first hash values as indexes and a sub-memory pointer table in which the memory addresses of the storage destinations of the fixed-length data are retained using the second hash values as indexes; and comparing means for simultaneously comparing a plurality of fixed-length data stored in the same memory addresses of the N memory banks and one fixed-length data input to the hash calculating means and outputting a comparison result.
Japanese patent JP08-235060A discloses that two tag memory addresses are simultaneously calculated by two different hash functions, first and second hash functions 64 and 66 respectively receive main memory addresses 60 as arguments and return values concerning tag memory addresses in a range of “0” to “n−1”, and n is the number of cache entries; in the first hash function 64 and the second hash function 66, F1(v), which is the first hash function 64, returns a value i to any argument v, F2(v), which is the second hash function 66, returns a value j to any argument v, and i and j are selected to be always different concerning a given bit value; in this example, a bit 10 is selected as a bit different between the value i and the value j; and such a bit having a different value between i and j can be used as a control bit.
Japanese patent JP07-168841A describes a hash table generating method for changing a value of a coefficient used for a hash value calculation and calculating a coefficient having smallest deviation of a hash value to thereby generate a hash table with high retrieval efficiency and memory use efficiency.